//
//  142. 环信链表II.swift
//  Top600
//
//  Created by rjb on 2021/8/9.
//

import Foundation
class Solution142 {
    // 环形链表求出入口点
    // 先通过快慢指针求出相遇点
    // 然后一个指针从相遇点出发，另一个指针从头开始出发，相遇时即为入口点
    func detectCycle(_ head: ListNode?) -> ListNode? {
        var slow = head
        var fast = head
        while fast != nil {
            slow = slow?.next
            fast = fast?.next?.next
            // 如果两个相等
            if slow === fast {
                slow = head
                while fast !== slow {
                    slow = slow?.next
                    fast = fast?.next
                }
                return slow
            }
        }
        return nil
    }
    
    static func test(){
        let solution = Solution142()
        let node3 = ListNode(3)
        let node2 = ListNode(2)
        let node0 = ListNode(0)
        let node4 = ListNode(-4)
        
        node3.next = node2
        node2.next = node0
        node0.next = node4
        node4.next = node2
        
        let result = solution.detectCycle(node3)
        print(result)
    }
    
}
